//
//  Vector_insert.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/5.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

/// 插入元素
extension Vector {
    /// insert after last element
    public func insert(_ element: Element) {
        insert(element, at: endIndex)
    }
    
    public func insert(_ element: Element, at index: Index) {
        precondition(index >= startIndex && index <= endIndex, "\(self)必须是连续存储空间")
        _expand()
        for i in (index..<endIndex).reversed() { _storage[i + 1] = _storage[i] }
        _storage[index] = element
        _size += 1
    }
    
    public func insert(contentsOf other: Vector<Element>, at index: Index) {
        precondition(index >= startIndex && index <= endIndex, "\(self)必须是连续存储空间")
        let insertedCount = other.count
        let oldSize = _size
        _size += insertedCount
        // 如有必要 扩容
        // 这里的扩容是特殊处理的
        // 既要保证容量得到扩充又不能访问坏内存
        if _size >= _capacity {
            _capacity = 2 * _size
            let newStorage = Allocator.allocate(_capacity, for: Element.self)
            for i in startIndex..<oldSize { newStorage[i] = _storage[i] }
            _storage.deallocate()
            _storage = newStorage
        }
        for i in (index..<endIndex).reversed() { _storage[i + insertedCount] = _storage[i] }
        for i in index..<(index + insertedCount) { _storage[i] = other[i - index] }
    }
}
